/**
 * 回溯法求解八皇后问题。
 */

#include <stdio.h>

#define CHESS_WIDTH 8
#define CHESS_HEIGHT 8

int chess[CHESS_WIDTH][CHESS_HEIGHT];
int queen[CHESS_HEIGHT];

int lastqueen = -1;

int solutions = 0;

void print_solution()
{
    puts("\n#####################");
    for (int i = 0; i < CHESS_WIDTH; i++)
    {
        for (int j = 0; j < CHESS_HEIGHT; j++)
        {
            if (j == queen[i])
            {
                printf("1 ");
            } 
            else
            {
                printf("0 ");
            }
            
        }
        puts("");
    }
    puts("\n#####################");
}

// 找指定的行是否有放皇后
// row：是指定的行
// start_col：起始列，从此列开始找
int find_position(int row, int start_col)
{
    for (int j = start_col; j < CHESS_HEIGHT; j++)
    {
        if (chess[row][j] == 0) 
        {
            return j;
        }
    }
    return -1;
    
}

/**
 * @brief 在指定的位置放置queen，放好以后，会将皇后所在的行，列，对角线加1，表示这些位置是皇后攻击范围
 *        chess中的数组元素如果等于-1，表示皇后所在位置
 *        chess中的数组元素如果等于0，表示该位置可以放置皇后
 *        chess中的数组元素如果大于0,，表示皇后所在位置处于已放置皇后的攻击范围，不能放置皇后
 * 
 * @param row 放置皇后的行
 * @param col 放置皇后的列
 */
void put_queen(int row, int col)
{
    chess[row][col] = -1;
    queen[row] = col;

    for (int i = 0; i < CHESS_WIDTH; i++)
    {
        if (chess[i][col] != -1)
        {
            chess[i][col]++;
        }
        
    }

    for (int j = 0; j < CHESS_HEIGHT; j++)
    {
        if (chess[row][j] != -1)
        {
            chess[row][j] ++;
        }
    }
    
    for (int i = row + 1, j = col + 1; i < CHESS_WIDTH && j < CHESS_HEIGHT; i++, j++)
    {
        chess[i][j]++;
    }
    
    for (int i = row + 1, j = col - 1; i < CHESS_WIDTH && j >= 0; i++, j--)
    {
        chess[i][j]++;
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < CHESS_HEIGHT; i--, j++)
    {
        chess[i][j]++;
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
    {
        chess[i][j]++;
    }
}

/**
 * @brief 取消放置皇后
 * 
 * @param row 取消放置皇后的行号
 * @param col 取消放置皇后的列号
 */
void take_queen(int row, int col)
{

    for (int i = 0; i < CHESS_WIDTH; i++)
    {
        if (chess[i][col] != -1)
        {
            chess[i][col]--;
        }
    }
    
    for (int j = 0; j < CHESS_HEIGHT; j++)
    {
        if (chess[row][j] != -1)
        {
            chess[row][j]--;
        }
    }

    for (int i = row + 1, j = col + 1; i < CHESS_WIDTH && j < CHESS_HEIGHT; i++, j++)
    {
        chess[i][j]--;
    }
    
    for (int i = row + 1, j = col - 1; i < CHESS_WIDTH && j >= 0; i++, j--)
    {
        chess[i][j]--;
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < CHESS_HEIGHT; i--, j++)
    {
        chess[i][j]--;
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
    {
        chess[i][j]--;
    }

    // 这个地方本来是皇后，为-1，现在将其设置为0，表示可以放置皇后
    chess[row][col] = 0;
}

int main(void)
{
    // 初始化都是0
    for (int i = 0; i < CHESS_WIDTH; i++)
    {
        for (int j = 0; j < CHESS_HEIGHT; j++)
        {
            chess[i][j] = 0;
        }
        
    }

    for (int i = 0; ;)
    {
        int position = find_position(i, lastqueen + 1);
        if (position == -1)
        {
            if (i == 0)
            {
                // 回溯完毕，跳出循环
                break;
            }
            // 如果不是第一行，那必定i > 0
            // 取消放置i - 1行，继续下次迭代
            take_queen(i - 1, queen[i - 1]);
            lastqueen = queen[i - 1];
            i--;
            continue;
        }
        else
        {
            // 如果找到了新的位置，在i，position放置皇后
            // 将lastqueen赋值为-1是为了下次从下一行的开头寻找放置位置。
            lastqueen = -1;
            put_queen(i, position);
            if (i == 7)
            {

                solutions++;
                // 取消放置皇后，以便再次寻找下一个可能放置的位置
                take_queen(i, position);
                lastqueen = position;
                continue;
            }
            i++;
        }
        
    }
    printf("共有%d种解法", solutions);
    return 0;
}